package leetcode.weekly.week313;

//Solution4Test
public class Solution4 {

	public int deleteString(String s) {
		if(s.length() == 1) {
			return 1;
		}
		int ans = 0;
		int p = 0;
		while (s.length() > 1 && p != -1) {
			s = s.substring(p);
			ans++;
			p = this.kmp(s);
		}
		return ans;
	}

	public int kmp(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
		int[] p = new int[len];
		int ans = -1;
		for (int i = 1, j = 0; i < len && j < len; i++) {
			while (j > 0 && chars[j] != chars[i]) {
				j = p[j - 1];
			}
			if (chars[i] == chars[j]) {
				j++;
			}
			p[i] = j;
			if (i + 1 == j * 2) {
				ans = j;
			}
		}
		return ans;
	}

}
